#include <ctime>
#include <random>
#include <unordered_set>
#include "FibonacciHeap.h"
#define BOOST_TEST_MAIN test
#include <boost/test/included/unit_test.hpp>

using namespace std;

#define Handle CFibonacciHeap<int, int>::CHandle

// Кидаем в кучу 1000 рандомных чисел,
// запоминаем значение вершины с наименьшим приоритетом,
// сравниваем его со значением, возвращаемым ExtractMin
BOOST_AUTO_TEST_CASE(Add_ExtractMin_Test)
{
    srand (1);
    // добиваемся, чтобы все приоритеты были разными
    // иначе MinPriority может вернуть значение
    // любой из из вершин с минимальным приоритетом
    // (если получилось несколько таких)
    unordered_set<int> differentPriorities;
    while (differentPriorities.size() != 1000)
    {
        differentPriorities.insert(abs(rand() % 10000));
    }

	CFibonacciHeap<int, int> heap;
    int minPriority = 10001;
    int minPriorityValue = 10001;
    while (!differentPriorities.empty())
    {
        int priority = *differentPriorities.begin();
        int value = rand() % 1000;
        if (priority < minPriority)
        {
            minPriority = priority;
            minPriorityValue = value;
        }
        heap.Add(value, priority);
        differentPriorities.erase(priority);
    }

	BOOST_CHECK_EQUAL(heap.ExtractMin(), minPriorityValue);
}

// ExtractMin из пустой кучи должен выбросить исключение
BOOST_AUTO_TEST_CASE(EmptyHeapExtractMin_Test)
{
    CFibonacciHeap<int, int> heap;
    BOOST_CHECK_THROW(heap.ExtractMin(), logic_error);
}

// Кидаем в кучу 1000 рандомных чисел,
// запоминаем хендл одной из вершин,
// понижаем у нее приоритет до гарантированно минимального,
// сравниваем значение в ней со значением,
// возвращаемым ExtractMin
BOOST_AUTO_TEST_CASE(DecreaseValue_Test)
{
    srand (1);

    unordered_set<int> differentPriorities;
    while (differentPriorities.size() != 1000)
    {
        differentPriorities.insert(abs(rand() % 10000));
    }

	CFibonacciHeap<int, int> heap;
    while (!differentPriorities.empty())
    {
        int prio = *differentPriorities.begin();
        int val = rand() % 1000;
        heap.Add(val, prio);
        differentPriorities.erase(prio);
    }
    int priority = 10001;
    int value = 10001;
    Handle h = heap.Add(value, priority);
    heap.DecreasePriority(h, -1);
    BOOST_CHECK_EQUAL(heap.ExtractMin(), value);
    // понижаем приоритет еще раз
    // наш хендл не должен быть невалидным
    BOOST_WARN_EQUAL(heap.DecreasePriority(h, -1000), ET_RottenHandle);
    // при попытке повысить приоритет должна выскакивать ошибка ET_TooBigPriority
    BOOST_CHECK_EQUAL(heap.DecreasePriority(h, -1), ET_TooBigPriority);
}

BOOST_AUTO_TEST_CASE(PopMin_Test)
{
    srand (1);

    unordered_set<int> differentPriorities;
    map<int, int> orderedPriorities; // хранит пары <ключ, значение> упорядоченными по ключу
    while (differentPriorities.size() != 1000)
    {
        differentPriorities.insert(abs(rand() % 10000));
    }

	CFibonacciHeap<int, int> heap;
    while (!differentPriorities.empty())
    {
        int prio = *differentPriorities.begin();
        int val = rand() % 1000;
        heap.Add(val, prio);
        orderedPriorities[prio] = val;
        differentPriorities.erase(prio);
    }

    // пока куча не пуста, извлекаем из нее элемент с минимальным приоритетом
    // и проверяем, действительно ли он минимальный
    while (!heap.IsEmpty())
    {
        // проверяем, равен ли минимуму в нашей куче реальному минимуму
        BOOST_CHECK_EQUAL(heap.ExtractMin(), (*orderedPriorities.begin()).second);
        orderedPriorities.erase(orderedPriorities.begin());
        heap.PopMin();
    }
}


